# -*- coding: utf-8 -*-            
# @Time : 2022/11/17 11:25
# @Author  : lining
# @FileName: 单调队列.py
"""
单调队列
（1）支持头部删除，尾部支持删除插入
（2）数据一直保持最新的，把候选项放到队列里，时间单调性（也有单调递减，单调递增）
（3）头部出界删除，尾部数据比当前新的数据小的删除
https://leetcode.cn/problems/sliding-window-maximum/
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解题思路：时间单调性，一直保持最新的，最大的数
（1）空队列时直接把数据保存
（2）判断头数据是否已经出界，出界就删除
（3）不是空队列时，把当前数据和队尾数据进行比较，当前数据比较大就把队尾元素删除，直到比当前数据大，再把当前数据加入队尾
（4）当遍历的数据个数大于k，就把对头数据加入结果集
"""
class Solution:
    def maxSlidingWindow(self, nums, k):
        # 存储下标
        index_ = []
        # 结果集
        result = []
        for a in range(len(nums)):
            # 已经过界的数据从头部删除
            while index_ and a >= index_[0] + k:
                del index_[0]
            # 非空，且当前数据比队尾大，删除队尾，把新数据加入队列
            while index_ and nums[a] > nums[index_[-1]]:
                index_.pop()
            index_.append(a)
            # 遍历数据大于等于三个，取出最大值放到结果集
            if a >= k - 1:
                result.append(nums[index_[0]])
        print(result)


nums = [1,3,-1,-3,5,3,6,7]
k = 3
Solution().maxSlidingWindow(nums, k)


